package marchingCubes;

import java.awt.geom.Line2D;
import java.util.Vector;

import simpleGeom.Bounds3D;
import simpleGeom.Box3D;
import simpleGeom.HasPos3D;
import simpleGeom.SimpleTriangle;
import simpleGeom.TriangleMath;
import simpleGeom.Vec3D;

public class VoxelizeFast {
	
		public DualCube[][][] cubes;
		float sX;
		float sY;
		float sZ;
		public float dimX;
		public float dimY;
		public float dimZ;
		public int nX;
		public int nY;
		public int nZ;
		float scale;
		public void init(Box3D b, float dim) {
			sX = b.x1;
			sY = b.y1;
			sZ = b.z1;
			dimX = dim;
			dimY = dim;
			dimZ = dim;
			//scale=1f/dim;
			nX = (int) (b.getDimX() / dim) + 1;
			nY = (int) (b.getDimY() / dim) + 1;
			nZ = (int) (b.getDimZ() / dim) + 1;
			System.out.println("nX: " + nX + " nY: " + nY + " nZ: " + nZ);
			cubes = new DualCube[nX][nY][nZ];
			init(nX, nY, nZ);
			/*
			 * for (int x = 0; x < nX; x++) { for (int y = 0; y < nY; y++) { for
			 * (int z = 0; z < nZ; z++) { DualCube dc = new DualCube();
			 * cubes[x][y][z]=dc; dc.edges = new DualEdge[3]; } } }
			 */

		}

		public void init(int nX, int nY, int nZ) {
			cubes = new DualCube[nX][nY][nZ];
			for (int x = 0; x < nX; x++) {
				for (int y = 0; y < nY; y++) {
					for (int z = 0; z < nZ; z++) {
						DualCube dc = new DualCube();
						dc.x = (short) x;
						dc.y = (short) y;
						dc.z = (short) z;
						dc.edges = new DualEdge[3];
						cubes[x][y][z] = dc;
					}
				}
			}
		}

		public DualEdge getEdge(int x1, int y1, int z1, int x2, int y2, int z2) {
			int sX = Math.min(x1, x2);
			int sY = Math.min(y1, y2);
			int sZ = Math.min(z1, z2);
			
			DualCube dc1 = cubes[sX][sY][sZ];
			if (dc1 == null) {
				return null;
			}
			if (x1 != x2) {
				return dc1.edges[0];
			}
			if (y1 != y2) {
				return dc1.edges[1];
			}
			return dc1.edges[2];
		}

		public DualEdge addEdge(int x1, int y1, int z1, int x2, int y2, int z2) {
			int sX = Math.min(x1, x2);
			int sY = Math.min(y1, y2);
			int sZ = Math.min(z1, z2);

			int eX = Math.max(x1, x2);
			int eY = Math.max(y1, y2);
			int eZ = Math.max(z1, z2);
			DualCube dc1 = cubes[sX][sY][sZ];
			if (dc1 == null) {
				dc1 = new DualCube();
				dc1.edges = new DualEdge[3];
				cubes[sX][sY][sZ] = dc1;
			}
			if (eX >= nX || eY >= nY || eZ >= nZ)
				return null;
			DualCube dc2 = cubes[eX][eY][eZ];
			if (dc2 == null) {
				dc2 = new DualCube();
				dc2.edges = new DualEdge[3];
				cubes[eX][eY][eZ] = dc2;
			}
			DualEdge dualEdge = new DualEdge(dc1, dc2);
			if (x1 != x2) {
				dc1.edges[0] = dualEdge;
			}

			if (y1 != y2) {
				dc1.edges[1] = dualEdge;
			}
			if (z1 != z2) {
				dc1.edges[2] = dualEdge;
			}
			return dualEdge;
		}

		int getXInt(float x) {
			float f= ((x - sX) / dimX);
			return (int) f;
		}

		int getYInt(float y) {
			return (int) ((y - sY) / dimY);
		}

		int getZInt(float z) {
			return (int) ((z - sZ) / dimZ);
		}

		public float getXFloat(float x) {
			return sX + x * dimX;
		}

		public float getYFloat(float y) {
			return sY + y * dimY;
		}

		public float getZFloat(float z) {
			return sZ + z * dimZ;
		}

		Vector<SimpleTriangle> triangles;

		public void scanTriangle(HasPos3D p1, HasPos3D p2, HasPos3D p3) {
			
			TriangleMath tri=new TriangleMath(p1,p2,p3);
			/*scanX(b3d, p1, p2, p3);
			scanY(b3d, p1, p2, p3);
			scanZ(b3d, p1, p2, p3);*/
			scanX2(tri);
			scanY2(tri);
			scanZ2(tri);
		}
		public void scanTriangle(float x1,float y1,float z1,float x2,float y2,float z2,float x3,float y3,float z3) {
			Vec3D p1=new Vec3D(x1,y1,z1);
			Vec3D p2=new Vec3D(x2,y2,z2);
			Vec3D p3=new Vec3D(x3,y3,z3);
			TriangleMath tri=new TriangleMath(p1,p2,p3);
			/*scanX(b3d, p1, p2, p3);
			scanY(b3d, p1, p2, p3);
			scanZ(b3d, p1, p2, p3);*/
			scanX2(tri);
			scanY2(tri);
			scanZ2(tri);
		}
		
		
		final static double SMALL_NUM = 0.0000000001f;

		
		public void scanX2(TriangleMath tri) {
			int y1 = Math.max(getYInt(tri.b3d.y1),0);
			int z1 = Math.max(getZInt(tri.b3d.z1),0);
			int y2 = Math.min(getYInt(tri.b3d.y2) + 2, nY);
			int z2 = Math.min(getZInt(tri.b3d.z2) + 2, nZ);// ok

			for (int y = y1; y < y2; y++) {
				for (int z = z1; z < z2; z++) {
					float fY = getYFloat(y);
					float fZ = getZFloat(z);
					HasPos3D r0 = new Vec3D(0, fY, fZ);
					HasPos3D r1 = new Vec3D(1f, fY, fZ);// ok
					Vec3D iP = tri.intersect_LineTriangle(r0, r1);
					if (iP != null) {
						int cX = getXInt(iP.x);
						DualEdge cEdge = addEdge(cX, y, z, cX + 1, y, z);
						if (cEdge != null) {
							cEdge.intersection = iP;
							cEdge.normal = tri.n;
						}
					}
				}
			}
		}

		public void scanY2(TriangleMath tri) {
			int x1 = Math.max(getXInt(tri.b3d.x1),0);
			int z1 = Math.max(getZInt(tri.b3d.z1),0);
			int x2 = Math.min(getXInt(tri.b3d.x2) + 2, nX);
			int z2 = Math.min(getZInt(tri.b3d.z2) + 2, nZ);// ok

			for (int x = x1; x < x2; x++) {
				for (int z = z1; z < z2; z++) {
					float fX = getXFloat(x);
					float fZ = getZFloat(z);
					HasPos3D r0 = new Vec3D(fX, 0, fZ);
					HasPos3D r1 = new Vec3D(fX, 1f, fZ);
					Vec3D iP = tri.intersect_LineTriangle(r0, r1);
					if (iP != null) {
						int cY = getYInt(iP.y);
						DualEdge cEdge = addEdge(x, cY, z, x, cY + 1, z);
						if (cEdge != null) {
							cEdge.intersection = iP;
							cEdge.normal = tri.n;
						}
					}
				}
			}
		}

		public void scanZ2(TriangleMath tri) {
			int x1 = Math.max(getXInt(tri.b3d.x1), 0);
			int y1 = Math.max(getYInt(tri.b3d.y1), 0);
			int x2 = Math.min(getXInt(tri.b3d.x2) + 2, nX);
			int y2 = Math.min(getYInt(tri.b3d.y2) + 2, nY);// ok

			for (int x = x1; x < x2; x++) {
				for (int y = y1; y < y2; y++) {
					float fX = getXFloat(x);
					float fY = getYFloat(y);
					HasPos3D r0 = new Vec3D(fX, fY, 0);
					HasPos3D r1 = new Vec3D(fX, fY, 1f);
					Vec3D iP = tri.intersect_LineTriangle(r0, r1);
					if (iP != null) {
						int cZ = getZInt(iP.z);
						DualEdge cEdge = addEdge(x, y, cZ, x, y, cZ + 1);
						if (cEdge != null) {
							cEdge.intersection = iP;
							cEdge.normal = tri.n;
						}
					}
				}
			}
		}
		
		

		
		

		public void calculateDepthWrong(boolean[][][] reached) {
			int nX = reached.length;
			int nY = reached[0].length;
			int nZ = reached[0][0].length;
			for (int z = 0; z < nZ - 1; z++) {
				for (int y = 0; y < nY - 1; y++) {
					for (int x = 0; x < nX - 1; x++) {
						boolean cDepth = reached[x][y][z];
						if (cDepth) {
							if (getEdge(x, y, z, x, y, z + 1) == null)
								reached[x][y][z + 1] = true;
							if (getEdge(x, y, z, x, y + 1, z) == null)
								reached[x][y + 1][z] = true;
							if (getEdge(x, y, z, x + 1, y, z) == null)
								reached[x + 1][y][z] = true;
						}
					}
				}
			}
			for (int z = nZ - 1; z > 0; z--) {

				for (int y = nY - 1; y > 0; y--) {
					for (int x = nX - 1; x > 0; x--) {
						boolean cDepth = reached[x][y][z];
						if (cDepth) {
							if (getEdge(x, y, z, x, y, z - 1) == null)
								reached[x][y][z - 1] = true;
							if (getEdge(x, y, z, x, y - 1, z) == null)
								reached[x][y - 1][z] = true;
							if (getEdge(x, y, z, x - 1, y, z) == null)
								reached[x - 1][y][z] = true;
						}
					}
				}
			}

		}

		public void calculateDepth(boolean[][][] reached) {
			Vector<DualCube> candidates = new Vector<DualCube>();
			for (int x = 0; x < nX - 1; x++) {
				for (int y = 0; y < nY - 1; y++) {
					for (int z = 0; z < nZ - 1; z++) {
						boolean cDepth = reached[x][y][z];
						if (cDepth) {
							DualCube dc = cubes[x][y][z];
							candidates.add(dc);
							dc.setInside(true);
						}
					}
				}
			}
			while (candidates.size() > 0) {
				Vector<DualCube> nextCandidates = new Vector<DualCube>();
				for (int i = 0; i < candidates.size(); i++) {
					DualCube cube = candidates.get(i);
					int x = cube.x;
					int y = cube.y;
					int z = cube.z;
					Vector<DualCube> nbs = new Vector<DualCube>();
					if (x < nX - 1)
						nbs.add(cubes[x + 1][y][z]);
					if (x > 0)
						nbs.add(cubes[x - 1][y][z]);
					if (y < nY - 1)
						nbs.add(cubes[x][y + 1][z]);
					if (y > 0)
						nbs.add(cubes[x][y - 1][z]);
					if (z < nZ - 1)
						nbs.add(cubes[x][y][z + 1]);
					if (z > 0)
						nbs.add(cubes[x][y][z - 1]);
					for (int j = 0; j < nbs.size(); j++) {
						DualCube nb = nbs.get(j);
						//&& getEdge(x, y, z, nb.x, nb.y, nb.z) == null
						if (!nb.isInside()) {
							if (getEdge(x, y, z, nb.x, nb.y, nb.z) == null){
								nb.setInside(true);
								boolean isBorder=this.isBorder(nb.x, nb.y, nb.z);
								//if (!isBorder){
								nextCandidates.add(nb);
								//}
							}
						}
						/*if (!nb.isInside()
								&& getEdge(x, y, z, nb.x, nb.y, nb.z) == null) {
							nb.setInside(true);
							nextCandidates.add(nb);
						}*/
					}
				}
				candidates = nextCandidates;
			}
		}

		public boolean isBorder(int x, int y, int z) {
			DualCube dC = cubes[x][y][z];
			DualCube[] nbs = new DualCube[6];
			nbs[0] = getCube(x + 1,y,z);
			nbs[1] = getCube(x,y + 1,z);
			nbs[2] = getCube(x - 1,y,z);
			nbs[3] = getCube(x,y - 1,z);
			nbs[4] =  getCube(x,y,z - 1);
			nbs[5] =  getCube(x,y,z + 1);
			int nE = 0;
			for (int i = 0; i < 6; i++) {
				DualCube nb = nbs[i];
				if (nb != null) {
					DualEdge dE = getEdge(dC.x, dC.y, dC.z, nb.x, nb.y, nb.z);
					if (dE != null) {
						nE++;
					}
				}
			}
			if (nE > 0)
				return true;
			return false;
		}
		public DualCube getCube(int x, int y, int z) {
			if (x >= nX || y >= nY || z >= nZ||x<0||y<0||z<0)
				return null;
			return cubes[x][y][z];
		}
		public Vec3D getCenter(DualCube[] corners ){
			DualCube c1=corners[0];
			return new Vec3D(c1.x+0.5f,c1.y+0.5f,c1.z+0.5f);
		}
		
		public Vec3D calculateMidPoint(int x1, int y1, int z1, int x2, int y2,
				int z2, float  v1,float v2, float iso) {
			
			Vec3D m = null;
			int dx = x2 - x1;
			int dy = y2 - y1;
			int dz = z2 - z1;
			float t = (iso - v1) / (v2 - v1);
			if (v1<iso!=v2<iso){
			//if (t >= 0 && t <= 1) {
				m = new Vec3D();
				m.x = (float) (x1 + t * dx);
				m.y = (float) (y1 + t * dy);
				m.z = (float) (z1 + t * dz);
			}
			return m;
		}
		
		
		
		public Vector<SimpleTriangle> getMCFaces() {
			
			// collect cubes
			for (int x = 0; x < nX ; x++) {
				for (int y = 0; y < nY ; y++) {
					for (int z = 0; z < nZ ; z++) {
						DualCube[] corners = new DualCube[8];
						corners[0] = getCube(x, y, z);
						corners[1] = getCube(x + 1, y, z);
						corners[2] = getCube(x + 1, y + 1, z);
						corners[3] = getCube(x, y + 1, z);

						corners[4] = getCube(x, y, z + 1);
						corners[5] = getCube(x + 1, y, z + 1);
						corners[6] = getCube(x + 1, y + 1, z + 1);
						corners[7] = getCube(x, y + 1, z + 1);
						
						
						int caseNumber = 0;
						for (int i = 7; i > -1; i--) {
							DualCube corner=corners[i];
							if (corner!=null&&corner.isInside()) {
								caseNumber++;
							}
							if (i > 0) {
								caseNumber = caseNumber << 1;
							}
						}
						corners[0].index=caseNumber;
					}
				}
			}
			// collect faces
			Vector<SimpleTriangle> faces = new Vector<SimpleTriangle>();
			for (int x = 0; x < nX - 1; x++) {
				for (int y = 0; y < nY - 1; y++) {
					for (int z = 0; z < nZ - 1; z++) {
						DualCube c = cubes[x][y][z];
						if (c != null) {
							DualCube cX = cubes[x + 1][y][z];
							DualCube cY = cubes[x][y + 1][z];
							DualCube cZ = cubes[x][y][z + 1];
							DualCube cYZ = cubes[x][y + 1][z + 1];
							DualCube cXZ = cubes[x + 1][y][z + 1];
							DualCube cXY = cubes[x + 1][y + 1][z];

							DualEdge[] edges = new DualEdge[12];
							if (cY != null)
								edges[0] = cY.edges[0];
							if (cX != null)
								edges[1] = cX.edges[1];
							edges[2] = c.edges[0];
							edges[3] = c.edges[1];
							if (cYZ != null)
								edges[4] = cYZ.edges[0];
							if (cXZ != null)
								edges[5] = cXZ.edges[1];
							if (cZ != null)
								edges[6] = cZ.edges[0];
							if (cZ != null)
								edges[7] = cZ.edges[1];
							if (cY != null)
								edges[8] = cY.edges[2];
							if (cXY != null)
								edges[9] = cXY.edges[2];
							edges[10] = c.edges[2];
							if (cX != null)
								edges[11] = cX.edges[2];
							int nEdges=0;
							for (int i=0;i<edges.length;i++){
								DualEdge edge=edges[i];
								if (edge!=null){
									nEdges++;
								}
							}
							
							int offset = c.index * 15;
							for (int i = offset; i < offset + 15; i += 3) {
								if (faceCode[i] > -1) {
									DualEdge[] vs = new DualEdge[3];
									vs[0] = edges[faceCode[i]];
									vs[1] = edges[faceCode[i + 1]];
									vs[2] = edges[faceCode[i + 2]];
									if (vs[0]!=null&&vs[1]!=null&&vs[2]!=null){
									SimpleTriangle f = new SimpleTriangle(vs[0].intersection,vs[1].intersection,vs[2].intersection);
									faces.add(f);
									}
									
								}
							}
						}
					}
				}
			}
			return faces;
		}


		
		
		private static int faceCode[] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 11,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 1, 2, 11,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 2, 11, 0, 2, 9, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, 2, 8, 3, 2, 11, 8, 11, 9, 8, -1, -1, -1,
			-1, -1, -1, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, 0, 10, 2, 8, 10, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 9,
			0, 2, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 10, 2, 1, 9,
			10, 9, 8, 10, -1, -1, -1, -1, -1, -1, 3, 11, 1, 10, 11, 3, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, 0, 11, 1, 0, 8, 11, 8, 10, 11, -1, -1,
			-1, -1, -1, -1, 3, 9, 0, 3, 10, 9, 10, 11, 9, -1, -1, -1, -1, -1,
			-1, 9, 8, 11, 11, 8, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 7,
			8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0, 7, 3,
			4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 8, 4, 7, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1,
			-1, -1, -1, 1, 2, 11, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			3, 4, 7, 3, 0, 4, 1, 2, 11, -1, -1, -1, -1, -1, -1, 9, 2, 11, 9, 0,
			2, 8, 4, 7, -1, -1, -1, -1, -1, -1, 2, 11, 9, 2, 9, 7, 2, 7, 3, 7,
			9, 4, -1, -1, -1, 8, 4, 7, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, 10, 4, 7, 10, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, 9, 0,
			1, 8, 4, 7, 2, 3, 10, -1, -1, -1, -1, -1, -1, 4, 7, 10, 9, 4, 10,
			9, 10, 2, 9, 2, 1, -1, -1, -1, 3, 11, 1, 3, 10, 11, 7, 8, 4, -1,
			-1, -1, -1, -1, -1, 1, 10, 11, 1, 4, 10, 1, 0, 4, 7, 10, 4, -1, -1,
			-1, 4, 7, 8, 9, 0, 10, 9, 10, 11, 10, 0, 3, -1, -1, -1, 4, 7, 10,
			4, 10, 9, 9, 10, 11, -1, -1, -1, -1, -1, -1, 9, 5, 4, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 5, 4, 0, 8, 3, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, 0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, 8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, 1,
			2, 11, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 8, 1, 2,
			11, 4, 9, 5, -1, -1, -1, -1, -1, -1, 5, 2, 11, 5, 4, 2, 4, 0, 2,
			-1, -1, -1, -1, -1, -1, 2, 11, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1,
			-1, -1, 9, 5, 4, 2, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0,
			10, 2, 0, 8, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, 0, 5, 4, 0, 1, 5,
			2, 3, 10, -1, -1, -1, -1, -1, -1, 2, 1, 5, 2, 5, 8, 2, 8, 10, 4, 8,
			5, -1, -1, -1, 11, 3, 10, 11, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1,
			-1, 4, 9, 5, 0, 8, 1, 8, 11, 1, 8, 10, 11, -1, -1, -1, 5, 4, 0, 5,
			0, 10, 5, 10, 11, 10, 0, 3, -1, -1, -1, 5, 4, 8, 5, 8, 11, 11, 8,
			10, -1, -1, -1, -1, -1, -1, 9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, 9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1,
			0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, 1, 5, 3, 3, 5,
			7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 7, 8, 9, 5, 7, 11, 1, 2,
			-1, -1, -1, -1, -1, -1, 11, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1,
			-1, -1, 8, 0, 2, 8, 2, 5, 8, 5, 7, 11, 5, 2, -1, -1, -1, 2, 11, 5,
			2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, 7, 9, 5, 7, 8, 9, 3, 10,
			2, -1, -1, -1, -1, -1, -1, 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 10, -1,
			-1, -1, 2, 3, 10, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, 10, 2, 1,
			10, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, 9, 5, 8, 8, 5, 7, 11, 1,
			3, 11, 3, 10, -1, -1, -1, 5, 7, 0, 5, 0, 9, 7, 10, 0, 1, 0, 11, 10,
			11, 0, 10, 11, 0, 10, 0, 3, 11, 5, 0, 8, 0, 7, 5, 7, 0, 10, 11, 5,
			7, 10, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, 6, 5, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 5, 11, 6, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, 9, 0, 1, 5, 11, 6, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, 1, 8, 3, 1, 9, 8, 5, 11, 6, -1, -1, -1, -1, -1, -1, 1,
			6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 6, 5, 1, 2,
			6, 3, 0, 8, -1, -1, -1, -1, -1, -1, 9, 6, 5, 9, 0, 6, 0, 2, 6, -1,
			-1, -1, -1, -1, -1, 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1,
			2, 3, 10, 11, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 0, 8,
			10, 2, 0, 11, 6, 5, -1, -1, -1, -1, -1, -1, 0, 1, 9, 2, 3, 10, 5,
			11, 6, -1, -1, -1, -1, -1, -1, 5, 11, 6, 1, 9, 2, 9, 10, 2, 9, 8,
			10, -1, -1, -1, 6, 3, 10, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1,
			0, 8, 10, 0, 10, 5, 0, 5, 1, 5, 10, 6, -1, -1, -1, 3, 10, 6, 0, 3,
			6, 0, 6, 5, 0, 5, 9, -1, -1, -1, 6, 5, 9, 6, 9, 10, 10, 9, 8, -1,
			-1, -1, -1, -1, -1, 5, 11, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, 4, 3, 0, 4, 7, 3, 6, 5, 11, -1, -1, -1, -1, -1, -1, 1, 9,
			0, 5, 11, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, 11, 6, 5, 1, 9, 7, 1,
			7, 3, 7, 9, 4, -1, -1, -1, 6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1,
			-1, -1, -1, 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, 8, 4,
			7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, 7, 3, 9, 7, 9, 4, 3, 2,
			9, 5, 9, 6, 2, 6, 9, 3, 10, 2, 7, 8, 4, 11, 6, 5, -1, -1, -1, -1,
			-1, -1, 5, 11, 6, 4, 7, 2, 4, 2, 0, 2, 7, 10, -1, -1, -1, 0, 1, 9,
			4, 7, 8, 2, 3, 10, 5, 11, 6, -1, -1, -1, 9, 2, 1, 9, 10, 2, 9, 4,
			10, 7, 10, 4, 5, 11, 6, 8, 4, 7, 3, 10, 5, 3, 5, 1, 5, 10, 6, -1,
			-1, -1, 5, 1, 10, 5, 10, 6, 1, 0, 10, 7, 10, 4, 0, 4, 10, 0, 5, 9,
			0, 6, 5, 0, 3, 6, 10, 6, 3, 8, 4, 7, 6, 5, 9, 6, 9, 10, 4, 7, 9, 7,
			10, 9, -1, -1, -1, 11, 4, 9, 6, 4, 11, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, 4, 11, 6, 4, 9, 11, 0, 8, 3, -1, -1, -1, -1, -1, -1, 11, 0,
			1, 11, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, 8, 3, 1, 8, 1, 6, 8,
			6, 4, 6, 1, 11, -1, -1, -1, 1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1,
			-1, -1, -1, 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, 0, 2,
			4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 3, 2, 8, 2, 4,
			4, 2, 6, -1, -1, -1, -1, -1, -1, 11, 4, 9, 11, 6, 4, 10, 2, 3, -1,
			-1, -1, -1, -1, -1, 0, 8, 2, 2, 8, 10, 4, 9, 11, 4, 11, 6, -1, -1,
			-1, 3, 10, 2, 0, 1, 6, 0, 6, 4, 6, 1, 11, -1, -1, -1, 6, 4, 1, 6,
			1, 11, 4, 8, 1, 2, 1, 10, 8, 10, 1, 9, 6, 4, 9, 3, 6, 9, 1, 3, 10,
			6, 3, -1, -1, -1, 8, 10, 1, 8, 1, 0, 10, 6, 1, 9, 1, 4, 6, 4, 1, 3,
			10, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, 6, 4, 8, 10, 6, 8,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 11, 6, 7, 8, 11, 8, 9, 11,
			-1, -1, -1, -1, -1, -1, 0, 7, 3, 0, 11, 7, 0, 9, 11, 6, 7, 11, -1,
			-1, -1, 11, 6, 7, 1, 11, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, 11, 6, 7,
			11, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, 1, 2, 6, 1, 6, 8, 1, 8,
			9, 8, 6, 7, -1, -1, -1, 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3,
			9, 7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, 7, 3, 2, 6,
			7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 10, 11, 6, 8, 11,
			8, 9, 8, 6, 7, -1, -1, -1, 2, 0, 7, 2, 7, 10, 0, 9, 7, 6, 7, 11, 9,
			11, 7, 1, 8, 0, 1, 7, 8, 1, 11, 7, 6, 7, 11, 2, 3, 10, 10, 2, 1,
			10, 1, 7, 11, 6, 1, 6, 7, 1, -1, -1, -1, 8, 9, 6, 8, 6, 7, 9, 1, 6,
			10, 6, 3, 1, 3, 6, 0, 9, 1, 10, 6, 7, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, 7, 8, 0, 7, 0, 6, 3, 10, 0, 10, 6, 0, -1, -1, -1, 7, 10, 6,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 6, 10, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 8, 10, 7, 6, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 10, 7, 6, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, 8, 1, 9, 8, 3, 1, 10, 7, 6, -1, -1, -1, -1, -1, -1,
			11, 1, 2, 6, 10, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 11,
			3, 0, 8, 6, 10, 7, -1, -1, -1, -1, -1, -1, 2, 9, 0, 2, 11, 9, 6,
			10, 7, -1, -1, -1, -1, -1, -1, 6, 10, 7, 2, 11, 3, 11, 8, 3, 11, 9,
			8, -1, -1, -1, 7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, 7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, 2, 7, 6, 2,
			3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, 1, 6, 2, 1, 8, 6, 1, 9, 8,
			8, 7, 6, -1, -1, -1, 11, 7, 6, 11, 1, 7, 1, 3, 7, -1, -1, -1, -1,
			-1, -1, 11, 7, 6, 1, 7, 11, 1, 8, 7, 1, 0, 8, -1, -1, -1, 0, 3, 7,
			0, 7, 11, 0, 11, 9, 6, 11, 7, -1, -1, -1, 7, 6, 11, 7, 11, 8, 8,
			11, 9, -1, -1, -1, -1, -1, -1, 6, 8, 4, 10, 8, 6, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, 3, 6, 10, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1,
			-1, 8, 6, 10, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, 9, 4, 6, 9,
			6, 3, 9, 3, 1, 10, 3, 6, -1, -1, -1, 6, 8, 4, 6, 10, 8, 2, 11, 1,
			-1, -1, -1, -1, -1, -1, 1, 2, 11, 3, 0, 10, 0, 6, 10, 0, 4, 6, -1,
			-1, -1, 4, 10, 8, 4, 6, 10, 0, 2, 9, 2, 11, 9, -1, -1, -1, 11, 9,
			3, 11, 3, 2, 9, 4, 3, 10, 3, 6, 4, 6, 3, 8, 2, 3, 8, 4, 2, 4, 6, 2,
			-1, -1, -1, -1, -1, -1, 0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, 1, 9,
			4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, 8, 1, 3, 8, 6, 1, 8,
			4, 6, 6, 11, 1, -1, -1, -1, 11, 1, 0, 11, 0, 6, 6, 0, 4, -1, -1,
			-1, -1, -1, -1, 4, 6, 3, 4, 3, 8, 6, 11, 3, 0, 3, 9, 11, 9, 3, 11,
			9, 4, 6, 11, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 5, 7, 6,
			10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 4, 9, 5, 10, 7, 6,
			-1, -1, -1, -1, -1, -1, 5, 0, 1, 5, 4, 0, 7, 6, 10, -1, -1, -1, -1,
			-1, -1, 10, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, 9, 5, 4,
			11, 1, 2, 7, 6, 10, -1, -1, -1, -1, -1, -1, 6, 10, 7, 1, 2, 11, 0,
			8, 3, 4, 9, 5, -1, -1, -1, 7, 6, 10, 5, 4, 11, 4, 2, 11, 4, 0, 2,
			-1, -1, -1, 3, 4, 8, 3, 5, 4, 3, 2, 5, 11, 5, 2, 10, 7, 6, 7, 2, 3,
			7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, 9, 5, 4, 0, 8, 6, 0, 6,
			2, 6, 8, 7, -1, -1, -1, 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1,
			-1, 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, 9, 5, 4, 11, 1, 6,
			1, 7, 6, 1, 3, 7, -1, -1, -1, 1, 6, 11, 1, 7, 6, 1, 0, 7, 8, 7, 0,
			9, 5, 4, 4, 0, 11, 4, 11, 5, 0, 3, 11, 6, 11, 7, 3, 7, 11, 7, 6,
			11, 7, 11, 8, 5, 4, 11, 4, 8, 11, -1, -1, -1, 6, 9, 5, 6, 10, 9,
			10, 8, 9, -1, -1, -1, -1, -1, -1, 3, 6, 10, 0, 6, 3, 0, 5, 6, 0, 9,
			5, -1, -1, -1, 0, 10, 8, 0, 5, 10, 0, 1, 5, 5, 6, 10, -1, -1, -1,
			6, 10, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, 1, 2, 11, 9, 5,
			10, 9, 10, 8, 10, 5, 6, -1, -1, -1, 0, 10, 3, 0, 6, 10, 0, 9, 6, 5,
			6, 9, 1, 2, 11, 10, 8, 5, 10, 5, 6, 8, 0, 5, 11, 5, 2, 0, 2, 5, 6,
			10, 3, 6, 3, 5, 2, 11, 3, 11, 5, 3, -1, -1, -1, 5, 8, 9, 5, 2, 8,
			5, 6, 2, 3, 8, 2, -1, -1, -1, 9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1,
			-1, -1, -1, -1, 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, 1, 5,
			6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 3, 6, 1, 6, 11,
			3, 8, 6, 5, 6, 9, 8, 9, 6, 11, 1, 0, 11, 0, 6, 9, 5, 0, 5, 6, 0,
			-1, -1, -1, 0, 3, 8, 5, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			11, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 5,
			11, 7, 5, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 5, 11, 10, 7,
			5, 8, 3, 0, -1, -1, -1, -1, -1, -1, 5, 10, 7, 5, 11, 10, 1, 9, 0,
			-1, -1, -1, -1, -1, -1, 11, 7, 5, 11, 10, 7, 9, 8, 1, 8, 3, 1, -1,
			-1, -1, 10, 1, 2, 10, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, 0, 8,
			3, 1, 2, 7, 1, 7, 5, 7, 2, 10, -1, -1, -1, 9, 7, 5, 9, 2, 7, 9, 0,
			2, 2, 10, 7, -1, -1, -1, 7, 5, 2, 7, 2, 10, 5, 9, 2, 3, 2, 8, 9, 8,
			2, 2, 5, 11, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, 8, 2, 0, 8,
			5, 2, 8, 7, 5, 11, 2, 5, -1, -1, -1, 9, 0, 1, 5, 11, 3, 5, 3, 7, 3,
			11, 2, -1, -1, -1, 9, 8, 2, 9, 2, 1, 8, 7, 2, 11, 2, 5, 7, 5, 2, 1,
			3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 7, 0, 7,
			1, 1, 7, 5, -1, -1, -1, -1, -1, -1, 9, 0, 3, 9, 3, 5, 5, 3, 7, -1,
			-1, -1, -1, -1, -1, 9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, 5, 8, 4, 5, 11, 8, 11, 10, 8, -1, -1, -1, -1, -1, -1, 5, 0,
			4, 5, 10, 0, 5, 11, 10, 10, 3, 0, -1, -1, -1, 0, 1, 9, 8, 4, 11, 8,
			11, 10, 11, 4, 5, -1, -1, -1, 11, 10, 4, 11, 4, 5, 10, 3, 4, 9, 4,
			1, 3, 1, 4, 2, 5, 1, 2, 8, 5, 2, 10, 8, 4, 5, 8, -1, -1, -1, 0, 4,
			10, 0, 10, 3, 4, 5, 10, 2, 10, 1, 5, 1, 10, 0, 2, 5, 0, 5, 9, 2,
			10, 5, 4, 5, 8, 10, 8, 5, 9, 4, 5, 2, 10, 3, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, 2, 5, 11, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, 5,
			11, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, 3, 11, 2, 3, 5,
			11, 3, 8, 5, 4, 5, 8, 0, 1, 9, 5, 11, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2,
			-1, -1, -1, 8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, 0,
			4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 4, 5, 8, 5,
			3, 9, 0, 5, 0, 3, 5, -1, -1, -1, 9, 4, 5, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, 4, 10, 7, 4, 9, 10, 9, 11, 10, -1, -1, -1,
			-1, -1, -1, 0, 8, 3, 4, 9, 7, 9, 10, 7, 9, 11, 10, -1, -1, -1, 1,
			11, 10, 1, 10, 4, 1, 4, 0, 7, 4, 10, -1, -1, -1, 3, 1, 4, 3, 4, 8,
			1, 11, 4, 7, 4, 10, 11, 10, 4, 4, 10, 7, 9, 10, 4, 9, 2, 10, 9, 1,
			2, -1, -1, -1, 9, 7, 4, 9, 10, 7, 9, 1, 10, 2, 10, 1, 0, 8, 3, 10,
			7, 4, 10, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, 10, 7, 4, 10, 4,
			2, 8, 3, 4, 3, 2, 4, -1, -1, -1, 2, 9, 11, 2, 7, 9, 2, 3, 7, 7, 4,
			9, -1, -1, -1, 9, 11, 7, 9, 7, 4, 11, 2, 7, 8, 7, 0, 2, 0, 7, 3, 7,
			11, 3, 11, 2, 7, 4, 11, 1, 11, 0, 4, 0, 11, 1, 11, 2, 8, 7, 4, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1,
			-1, -1, -1, -1, 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, 4,
			0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 8, 7, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 11, 8, 11, 10, 8, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 9, 3, 9, 10, 10, 9, 11, -1,
			-1, -1, -1, -1, -1, 0, 1, 11, 0, 11, 8, 8, 11, 10, -1, -1, -1, -1,
			-1, -1, 3, 1, 11, 10, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1,
			2, 10, 1, 10, 9, 9, 10, 8, -1, -1, -1, -1, -1, -1, 3, 0, 9, 3, 9,
			10, 1, 2, 9, 2, 10, 9, -1, -1, -1, 0, 2, 10, 8, 0, 10, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, 3, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, 2, 3, 8, 2, 8, 11, 11, 8, 9, -1, -1, -1, -1, -1,
			-1, 9, 11, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 8,
			2, 8, 11, 0, 1, 8, 1, 11, 8, -1, -1, -1, 1, 11, 2, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, 1, 3, 8, 9, 1, 8, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, 0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
			-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };

	
}
